#include <iostream>
#include <cstdlib>
using namespace std;
/* 
单链表的插入排序
 */
typedef struct lnode
{
    int data;
    struct lnode *next;
} lnode, *linklist;
int a[] = {9, 8, 7, 6, 5, 4, 3, 2, 1};

void makelist(linklist &l)
{
    lnode *r, *s;
    l = (lnode *)malloc(sizeof(lnode));
    l->next = nullptr;
    r = l;
    for (int i = 0; i < sizeof(a) / sizeof(int); i++)
    {
        s = (lnode *)malloc(sizeof(lnode));
        s->data = a[i];
        s->next = nullptr;
        r->next = s;
        r = s;
    }
    r = nullptr;
}

void printlist(linklist l)
{
    lnode *p = l->next;
    while (p)
    {
        cout << p->data << " ";
        p = p->next;
        /* code */
    }
    cout << endl;
}
// 插入排序
void sort(linklist &l)
{
    lnode *pre, *p = l->next, *r = p->next;
    // 将第一个结点摘下来,当作有序表
    p->next = nullptr;
    // p指向剩下的表的第一个元素
    p = r;
    while (p)
    {
        // r指向p的后继
        r = p->next;
        pre = l;
        while (pre->next != nullptr && pre->next->data < p->data)
        {
            // 找出原表中比有序表中p的小的结点pre
            pre = pre->next;
        }
        // 把p下入到pre后面
        p->next = pre->next;
        pre->next = p;
        // 指针后移
        p = r;
    }
}
int main(int argc, char const *argv[])
{
    linklist l;
    makelist(l);
    printlist(l);
    sort(l);
    printlist(l);
    exit(0);
    // return 0;
}
